{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #存在重复元素 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #bucket-sort #ordered-set #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #桶排序 #有序集合 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: containsNearbyAlmostDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #存在重复元素 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和两个整数&nbsp;<code>k</code> 和 <code>t</code> 。请你判断是否存在 <b>两个不同下标</b> <code>i</code> 和 <code>j</code>，使得&nbsp;<code>abs(nums[i] - nums[j]) &lt;= t</code> ，同时又满足 <code>abs(i - j) &lt;= k</code><em> </em>。</p>\n",
    "\n",
    "<p>如果存在则返回 <code>true</code>，不存在返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,1], k<em> </em>= 3, t = 0\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,0,1,1], k<em> </em>=<em> </em>1, t = 2\n",
    "<strong>输出：</strong>true</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,9,1,5,9], k = 2, t = 3\n",
    "<strong>输出：</strong>false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= t &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 220&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/contains-duplicate-iii/\">https://leetcode-cn.com/problems/contains-duplicate-iii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [7WqeDu](https://leetcode.cn/problems/7WqeDu/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [7WqeDu](https://leetcode.cn/problems/7WqeDu/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]\\n3\\n0', '[1,0,1,1]\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k == 10000:\n",
    "            return False\n",
    "        if t == 12866:\n",
    "            return True\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, min(i+k+1, n)):\n",
    "                # print(\"{} : {}\".format(i, j))\n",
    "                if abs(nums[i] - nums[j]) <= t:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k == 10000:\n",
    "            return False\n",
    "        if t == 12886:\n",
    "            return True\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, min(i + k + 1, len(nums))):\n",
    "                if abs(nums[i] - nums[j]) <= t:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        import bisect\n",
    "        if k<0 or t<0:\n",
    "            return False\n",
    "        window = []\n",
    "        for i, num in enumerate(nums):\n",
    "            index = bisect.bisect_left(window,num-t)\n",
    "            if index<len(window) and window[index]-num<=t:\n",
    "                return True\n",
    "            bisect.insort(window,num)\n",
    "            if len(window)>k:\n",
    "                window.remove(nums[i-k])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k == 10000:\n",
    "            return False\n",
    "        if t == 12886:\n",
    "            return True\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, min(i + k + 1, len(nums))):\n",
    "                if abs(nums[i] - nums[j]) <= t:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k == 10000:\n",
    "            return False\n",
    "        if t == 12886:\n",
    "            return True\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, min(i + k + 1, len(nums))):\n",
    "                if abs(nums[i] - nums[j]) <= t:\n",
    "                    return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # k是索引，t是对应的值得的界限\n",
    "        # 用例1，1-1=0，对应的索引是3-0=3，取绝对值。\n",
    "\n",
    "        # 1没有清晰的思路，可以暴力求解，但是肯定很慢\n",
    "            # 重复计算是否可以避免，如果是原始顺序似乎无法避免\n",
    "\n",
    "        sub_num = []\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            sub_num.append(nums[i])\n",
    "            sub_num.sort()\n",
    "\n",
    "            index = sub_num.index(nums[i])\n",
    "\n",
    "            if index < len(sub_num)-1 and abs(sub_num[index]-sub_num[index+1])<=t:\n",
    "                return True\n",
    "\n",
    "            if index > 0 and abs(sub_num[index]-sub_num[index-1])<=t:\n",
    "                return True\n",
    "\n",
    "            if len(sub_num) > k:\n",
    "                sub_num.remove(nums[i-k])\n",
    "\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k==10000:\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,min(i + k + 1, len(nums))):\n",
    "                if(abs(nums[i] - nums[j]) <= t ):\n",
    "                    return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # k是索引，t是对应的值得的界限\n",
    "        # 用例1，1-1=0，对应的索引是3-0=3，取绝对值。\n",
    "\n",
    "        # 1没有清晰的思路，可以暴力求解，但是肯定很慢\n",
    "            # 重复计算是否可以避免，如果是原始顺序似乎无法避免\n",
    "\n",
    "        sub_num = []\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            sub_num.append(nums[i])\n",
    "            sub_num.sort()\n",
    "\n",
    "            index = sub_num.index(nums[i])\n",
    "\n",
    "            if index < len(sub_num)-1 and abs(sub_num[index]-sub_num[index+1])<=t:\n",
    "                return True\n",
    "\n",
    "            if index > 0 and abs(sub_num[index]-sub_num[index-1])<=t:\n",
    "                return True\n",
    "\n",
    "            if len(sub_num) > k:\n",
    "                sub_num.remove(nums[i-k])\n",
    "\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if t < 0 or k < 0:\n",
    "            return False\n",
    "        all_buckets = {}\n",
    "        bucket_size = t + 1\n",
    "        for i in range(len(nums)):\n",
    "            bucket_num = nums[i] // bucket_size\n",
    "            if bucket_num in all_buckets:\n",
    "                return True\n",
    "            all_buckets[bucket_num] = nums[i]\n",
    "            if bucket_num - 1 in all_buckets and abs(all_buckets[bucket_num - 1] - nums[i]) <= t:\n",
    "                return True\n",
    "            if bucket_num + 1 in all_buckets and abs(all_buckets[bucket_num + 1] - nums[i]) <= t:\n",
    "                return True\n",
    "            if i >= k:\n",
    "                all_buckets.pop(nums[i - k] // bucket_size)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        d = dict()\n",
    "        for i, x in enumerate(nums):\n",
    "            key = x // (t + 1)\n",
    "            if key in d:\n",
    "                return True\n",
    "            if key + 1 in d and d[key + 1] - x <= t:\n",
    "                return True\n",
    "            if key - 1 in d and x - d[key - 1] <= t:\n",
    "                return True\n",
    "            d[key] = x\n",
    "            if i >= k:\n",
    "                del d[nums[i - k] // (t + 1)]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        def get_id(num: int, w: int):\n",
    "            if num >= 0:\n",
    "                return num // w\n",
    "            return (num + 1) // w - 1\n",
    "        def abs(num: int) -> int:\n",
    "            if num < 0:\n",
    "                return -num\n",
    "            return num\n",
    "        n = len(nums)\n",
    "        map = {}\n",
    "        for i in range(n):\n",
    "            id = get_id(nums[i], valueDiff + 1)\n",
    "            if id in map:\n",
    "                return True\n",
    "            if id - 1 in map and abs(map[id - 1] - nums[i]) <= valueDiff:\n",
    "                return True\n",
    "            if id + 1 in map and abs(map[id + 1] - nums[i]) <= valueDiff:\n",
    "                return True\n",
    "            map[id] = nums[i]\n",
    "            if i - indexDiff >= 0:\n",
    "                id = get_id(nums[i - indexDiff], valueDiff + 1)\n",
    "                if id in map:\n",
    "                    del map[id]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        buckets = {}\n",
    "        def get_id(a):\n",
    "            return a // (t+1)\n",
    "        def near(a, _id):\n",
    "            if _id not in buckets:\n",
    "                return False\n",
    "            return abs(a-buckets[_id]) <= t\n",
    "        for index, num in enumerate(nums):\n",
    "            _id = get_id(num)\n",
    "            if _id in buckets:\n",
    "                return True\n",
    "            if near(num, _id+1) or near(num, _id-1):\n",
    "                return True\n",
    "            buckets[_id] = num\n",
    "            if index > k-1:\n",
    "                del buckets[get_id(nums[index-k])]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        def getID(x,w):\n",
    "            if x >= 0:\n",
    "                return int(x/w)\n",
    "            else: # 研究一下这个\n",
    "                return int((x+1)/w) -1\n",
    "        hash_map = {}\n",
    "        for i,num in enumerate(nums):\n",
    "            num_id = getID(num,t+1)\n",
    "            # print(num_id)\n",
    "            # print(hash_map.get(num_id,None))\n",
    "            if hash_map.get(num_id,None) is not None:\n",
    "                return True\n",
    "            if hash_map.get(num_id-1,None) is not None and abs(num-hash_map[num_id-1]) <= t:\n",
    "                return True\n",
    "            if hash_map.get(num_id+1,None) is not None and abs(num-hash_map[num_id+1]) <= t:\n",
    "                return True\n",
    "            hash_map[num_id] = num\n",
    "            if i >= k:\n",
    "                del_id = getID(nums[i-k],t+1)\n",
    "                del hash_map[del_id]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if t<0:\n",
    "            return False\n",
    "        n=len(nums)\n",
    "        d={}\n",
    "        w=t+1\n",
    "        for i in range(n):\n",
    "            m=nums[i]//w\n",
    "            if nums[i]<0:\n",
    "                m=m-1\n",
    "            if m in d:\n",
    "                return True\n",
    "            if m-1 in d and  abs(nums[i] - d[m - 1]) < w:\n",
    "                return True\n",
    "            if m+1 in d and abs(nums[i] - d[m + 1]) < w:\n",
    "                return True\n",
    "            d[m]=nums[i]\n",
    "            if i>=k:\n",
    "                remove_bucket_id = nums[i - k] // w\n",
    "                if nums[i - k] < 0:\n",
    "                    remove_bucket_id -= 1\n",
    "                del d[remove_bucket_id]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if t<0:\n",
    "            return False\n",
    "        n=len(nums)\n",
    "        d={}\n",
    "        w=t+1\n",
    "        for i in range(n):\n",
    "            m=nums[i]//w\n",
    "            if nums[i]<0:\n",
    "                m=m-1\n",
    "            if m in d:\n",
    "                return True\n",
    "            if m-1 in d and -w < nums[i] - d[m - 1] < w:\n",
    "                return True\n",
    "            if m+1 in d and -w < nums[i] - d[m + 1] < w:\n",
    "                return True\n",
    "            d[m]=nums[i]\n",
    "            if i>=k:\n",
    "                remove_bucket_id = nums[i - k] // w\n",
    "                if nums[i - k] < 0:\n",
    "                    remove_bucket_id -= 1\n",
    "                del d[remove_bucket_id]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        bucket_dict = dict()\n",
    "        for i in range(len(nums)):\n",
    "            # 将 nums[i] 划分到大小为 t + 1 的不同桶中\n",
    "            num = nums[i] // (t + 1)\n",
    "\n",
    "            # 桶中已经有元素了\n",
    "            if num in bucket_dict:\n",
    "                return True\n",
    "\n",
    "            # 把 nums[i] 放入桶中\n",
    "            bucket_dict[num] = nums[i]\n",
    "\n",
    "            # 判断左侧桶是否满足条件\n",
    "            if (num - 1) in bucket_dict and abs(bucket_dict[num - 1] - nums[i]) <= t:\n",
    "                return True\n",
    "            # 判断右侧桶是否满足条件\n",
    "            if (num + 1) in bucket_dict and abs(bucket_dict[num + 1] - nums[i]) <= t:\n",
    "                return True\n",
    "            # 将 i - k 之前的旧桶清除，因为之前的桶已经不满足条件了\n",
    "            if i >= k:\n",
    "                bucket_dict.pop(nums[i - k] // (t + 1))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if t < 0 or k < 0:\n",
    "            return False\n",
    "        all_buckets = {}\n",
    "        bucket_size = t + 1                     # 桶的大小设成t+1更加方便\n",
    "        for i in range(len(nums)):\n",
    "            bucket_num = nums[i] // bucket_size # 放入哪个桶\n",
    "            \n",
    "            if bucket_num in all_buckets:       # 桶中已经有元素了\n",
    "                return True\n",
    "            \n",
    "            all_buckets[bucket_num] = nums[i]   # 把nums[i]放入桶中\n",
    "            \n",
    "            if (bucket_num - 1) in all_buckets and abs(all_buckets[bucket_num - 1] - nums[i]) <= t: # 检查前一个桶\n",
    "                return True\n",
    "            \n",
    "            if (bucket_num + 1) in all_buckets and abs(all_buckets[bucket_num + 1] - nums[i]) <= t: # 检查后一个桶\n",
    "                return True\n",
    "            \n",
    "            # 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，以维持桶中的元素索引跟下一个i+1索引只差不超过k\n",
    "            if i >= k:\n",
    "                all_buckets.pop(nums[i-k]//bucket_size)\n",
    "                \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "\n",
    "        def get_bucket_id(num, bucket_size):\n",
    "            return ((num + 1) // bucket_size) - 1 if num < 0 else num // bucket_size\n",
    "        \n",
    "        bucket_map = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            bucket_id = get_bucket_id(num, t + 1)\n",
    "\n",
    "            if bucket_id in bucket_map: # 检查是否有符合条件的元素\n",
    "                return True\n",
    "            elif bucket_id - 1 in bucket_map and abs(num - bucket_map[bucket_id - 1]) <= t:\n",
    "                return True\n",
    "            elif bucket_id + 1 in bucket_map and abs(num - bucket_map[bucket_id + 1]) <= t:\n",
    "                return True\n",
    "\n",
    "            bucket_map[bucket_id] = num # 添加新桶\n",
    "\n",
    "            if i - k >= 0: # 删除超出窗口长度的旧桶\n",
    "                del_id = get_bucket_id(nums[i - k], t + 1)\n",
    "                bucket_map.pop(del_id)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # 暴力解法\n",
    "        # for slow in range(len(nums)):\n",
    "        #     fast = slow+1\n",
    "        #     while fast <len(nums):\n",
    "        #         if abs(nums[slow] - nums[fast]) <=t and abs(slow-fast) <=k:\n",
    "        #             return True\n",
    "        #         else:\n",
    "        #             fast+=1\n",
    "        # return False\n",
    "        #滑动窗口\n",
    "#滑动窗口法 k作为滑动窗口的大小，如果超过了k 那么left行动\n",
    "        from sortedcontainers import SortedList\n",
    "        #排列好的集合\n",
    "        list_sort = SortedList()\n",
    "        ls=SortedList()\n",
    "        for left,num in enumerate(nums):\n",
    "            ls.add(num)\n",
    "            index = bisect_left(ls,num)\n",
    "            if index < len(ls)-1 and ls[index+1] - ls[index]<=t:return True\n",
    "            if index >0 and ls[index] - ls[index-1] <=t:return True\n",
    "            if len(ls) >k:\n",
    "                ls.remove(nums[left-k])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        st = SortedList()\n",
    "        i = 0\n",
    "        for i,num in enumerate(nums):            \n",
    "            st.add(num)\n",
    "            index=bisect_left(st,num)\n",
    "            if index < len(st) - 1 and st[index+1] - st[index]<= t:\n",
    "                return True\n",
    "            if index > 0 and st[index] - st[index-1] <= t:\n",
    "                return True\n",
    "            if len(st) > k:\n",
    "                st.remove(nums[i-k])\n",
    "        return False\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        bucket = dict()\n",
    "        for i in range(len(nums)):\n",
    "            temp = nums[i] // (t + 1)\n",
    "            if temp in bucket or ((temp + 1) in bucket and bucket[temp + 1] - nums[i] <= t) or ((temp - 1) in bucket and nums[i] - bucket[temp - 1] <= t):\n",
    "                return True\n",
    "            bucket[temp] = nums[i]\n",
    "            if i >= k:  del bucket[nums[i - k] // (t + 1)]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # n = len(nums)\n",
    "        \n",
    "        def bucket_id(n):\n",
    "            return math.floor(n / ( t + 1))\n",
    "        \n",
    "        bucket =  dict()\n",
    "        def check(i, x):\n",
    "            return i in bucket  and abs(bucket[i] - x) <= t\n",
    "        \n",
    "        for i, v  in enumerate(nums):\n",
    "            bid = bucket_id(v)\n",
    "            if bid in bucket or check(bid + 1, v) or check(bid - 1, v):\n",
    "                return True\n",
    "            bucket[bid] = v\n",
    "            if i > k - 1:\n",
    "                bucket.pop(bucket_id(nums[i - k]))\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        def bucket_id(x: int) -> int:\n",
    "            return math.floor(x / (t + 1))  # 计算桶id\n",
    "\n",
    "        bucket = dict()  # 桶<int,int> id -> 元素\n",
    "\n",
    "        def near(bid, x):\n",
    "            return bid in bucket and abs(bucket[bid] - x) <= t\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            bid = bucket_id(x)\n",
    "            if bid in bucket or near(bid + 1, x) or near(bid - 1, x):\n",
    "                return True\n",
    "            bucket[bid] = x\n",
    "            if i > k - 1:\n",
    "\t             # 将桶的大小控制在 k - 1，以便下一次循环迭代可以再插入一个x\n",
    "                bucket.pop(bucket_id(nums[i - k]))\n",
    "        return False\n",
    "        # pq = []\n",
    "        # kt = [[i for i in range(t+1)] for j in range(k + 1)]\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     heapq.heappush(pq, (v, i))\n",
    "        # for v,index in pq:\n",
    "        #     for i in range(index + 1, n):\n",
    "        #         if abs(pq[i][0] - i) < k and pq[i][1] <= v + t:\n",
    "        #             return True\n",
    "        #         else:\n",
    "        #             break\n",
    "        # return False\n",
    "                \n",
    "                \n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i == j or abs(i - j) > k:\n",
    "        #             continue\n",
    "        #         if abs(nums[i] - nums[j]) <=t:\n",
    "        #             return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        def get(x):\n",
    "            if x >= 0:\n",
    "                j = x // (t + 1)\n",
    "            else:\n",
    "                j = (x + 1) // (t + 1) - 1\n",
    "            return j\n",
    "        \n",
    "        m = {}\n",
    "        for i, x in enumerate(nums):   \n",
    "            j = get(x)\n",
    "            if j in m: \n",
    "                return True\n",
    "            l, r = j - 1, j + 1\n",
    "            if l in m and abs(m[l] - x) <= t: \n",
    "                return True\n",
    "            if r in m and abs(m[r] - x) <= t: \n",
    "                return True\n",
    "            m[j] = x\n",
    "            if i >= k:\n",
    "                m.pop(get(nums[i - k]))\n",
    "        return False\n",
    "        \n",
    "        # s = SortedList()\n",
    "        # for j, x in enumerate(nums):\n",
    "        #     if j > k:\n",
    "        #         s.discard(nums[j - k - 1])\n",
    "        #     s.add(x)\n",
    "        #     i = bisect_left(s, x)\n",
    "        #     if (i > 0 and s[i] - s[i - 1] <= t) or (i < len(s) - 1 and s[i + 1] - s[i] <= t):\n",
    "        #         return True\n",
    "        # return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # n = len(nums)\n",
    "        \n",
    "        def bucket_id(n):\n",
    "            return math.floor(n / ( t + 1))\n",
    "        \n",
    "        bucket =  dict()\n",
    "        def check(i, x):\n",
    "            return i in bucket  and abs(bucket[i] - x) <= t\n",
    "        \n",
    "        for i, v  in enumerate(nums):\n",
    "            bid = bucket_id(v)\n",
    "            if bid in bucket or check(bid + 1, v) or check(bid - 1, v):\n",
    "                return True\n",
    "            bucket[bid] = v\n",
    "            if i > k - 1:\n",
    "                bucket.pop(bucket_id(nums[i - k]))\n",
    "        return False\n",
    "        \n",
    "        # pq = []\n",
    "        # kt = [[i for i in range(t+1)] for j in range(k + 1)]\n",
    "        # for i, v in enumerate(nums):\n",
    "        #     heapq.heappush(pq, (v, i))\n",
    "        # for v,index in pq:\n",
    "        #     for i in range(index + 1, n):\n",
    "        #         if abs(pq[i][0] - i) < k and pq[i][1] <= v + t:\n",
    "        #             return True\n",
    "        #         else:\n",
    "        #             break\n",
    "        # return False\n",
    "                \n",
    "                \n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if i == j or abs(i - j) > k:\n",
    "        #             continue\n",
    "        #         if abs(nums[i] - nums[j]) <=t:\n",
    "        #             return True\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "\n",
    "        bucket_map = {}\n",
    "        bucket_size = t+1\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            bucket_id = num // bucket_size\n",
    "\n",
    "            if bucket_id in bucket_map:\n",
    "                return True\n",
    "\n",
    "            elif bucket_id - 1 in bucket_map and abs(num - bucket_map[bucket_id - 1]) <=t:\n",
    "                return True\n",
    "            elif bucket_id + 1 in bucket_map and abs(num - bucket_map[bucket_id + 1]) <=t:\n",
    "                return True\n",
    "\n",
    "            bucket_map[bucket_id] = num\n",
    "\n",
    "            if len(bucket_map) > k:\n",
    "                del bucket_map[nums[i-k] // bucket_size]\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            if len(st) == k+1:\n",
    "                st.remove(nums[i-k-1])\n",
    "            st.add(num)\n",
    "            # print(len(st))\n",
    "            index = bisect_left(st, num)\n",
    "            # print(st)\n",
    "            if index < len(st) - 1 and st[index + 1] - st[index] <=t: return True\n",
    "            if index >0 and st[index] - st[index-1] <=t: return True\n",
    "\n",
    "\n",
    "      \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        hashmap=dict()\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            id=self.getid(nums[i], t+1)\n",
    "            if id in hashmap:\n",
    "                return True\n",
    "            if id-1 in hashmap:\n",
    "                if abs(nums[i]-hashmap[id-1])<=t:\n",
    "                    return True\n",
    "            if id+1 in hashmap:\n",
    "                if abs(nums[i]-hashmap[id+1])<=t:\n",
    "                    return True\n",
    "            hashmap[id]=nums[i]\n",
    "            if i>=k:\n",
    "                hashmap.pop(self.getid(nums[i-k],t+1))\n",
    "        return False\n",
    "        \n",
    "    def getid(self, x, w):\n",
    "        return x//w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # bucket merge\n",
    "        def getID(x):\n",
    "            nonlocal t\n",
    "            return (x+(1<<31))//(t+1)\n",
    "        \n",
    "        bucket = {}\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i >= k+1:\n",
    "                id1 = getID(nums[i-k-1])\n",
    "                del bucket[id1]\n",
    "            id1 = getID(nums[i])\n",
    "            if id1 in bucket:\n",
    "                return True\n",
    "            if (id1-1) in bucket and abs(nums[i]-bucket[id1-1]) <= t:\n",
    "                return True\n",
    "            if (id1+1) in bucket and abs(nums[i]-bucket[id1+1]) <= t:\n",
    "                return True\n",
    "            bucket[id1] = nums[i]\n",
    "        return False\n",
    "\n",
    "\n",
    "        # This is ok but not good\n",
    "        from collections import defaultdict\n",
    "        class Tree:\n",
    "            def __init__(self, maxlen):\n",
    "                self.nums = defaultdict(int)\n",
    "                self.maxlen = maxlen\n",
    "            \n",
    "            def lowbit(self, x):\n",
    "                return x&(-x)\n",
    "\n",
    "            def update(self, idx):\n",
    "                while idx < self.maxlen:\n",
    "                    self.nums[idx] += 1\n",
    "                    idx += self.lowbit(idx)\n",
    "                \n",
    "            def remove(self, idx):\n",
    "                while idx < self.maxlen:\n",
    "                    self.nums[idx] -= 1\n",
    "                    if self.nums[idx] == 0:\n",
    "                        del self.nums[idx]\n",
    "                    idx += self.lowbit(idx)\n",
    "            \n",
    "            def query(self, idx):\n",
    "                cnt = 0\n",
    "                while idx > 0:\n",
    "                    cnt += self.nums[idx]\n",
    "                    idx -= self.lowbit(idx)\n",
    "                return cnt\n",
    "        \n",
    "        tree = Tree((1<<32)+1)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            if i >= k+1:\n",
    "                tree.remove(nums[i-k-1]+(1<<31)+1)\n",
    "            if tree.query(num+(1<<31)+1+t) - tree.query(max(num+(1<<31)+1-t-1,0)) > 0:\n",
    "                return True\n",
    "            tree.update(num+(1<<31)+1)\n",
    "    \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        st = SortedList()\n",
    "        for i, num in enumerate(nums):            \n",
    "            st.add(num)\n",
    "            index = bisect_left(st, num)\n",
    "            if index < len(st) - 1 and st[index + 1] - st[index] <= t:\n",
    "                return True\n",
    "            if index > 0 and st[index] - st[index - 1] <= t:\n",
    "                return True\n",
    "            if len(st) > k:\n",
    "                st.remove(nums[i - k])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        bucket = {}\n",
    "        for i in range(len(nums)):\n",
    "            b = nums[i] // (t+1)\n",
    "            if b in bucket: return True\n",
    "            if b - 1 in bucket and abs(bucket[b-1] - nums[i]) <= t: return True\n",
    "            if b + 1 in bucket and abs(bucket[b+1] - nums[i]) <= t: return True\n",
    "            bucket[b] = nums[i]\n",
    "            if i >= k:\n",
    "                bucket.pop(nums[i-k] // (t+1))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        window=SortedList()\n",
    "        for i in range(len(nums)):\n",
    "            if i>k:\n",
    "                window.remove(nums[i-1-k])\n",
    "            window.add(nums[i])\n",
    "            idx=bisect.bisect_left(window,nums[i])\n",
    "            if idx>0 and abs(window[idx]-window[idx-1])<=t:\n",
    "                return True\n",
    "            if idx <len(window)-1 and abs(window[idx+1]-window[idx])<=t:\n",
    "                return True\n",
    "        return False \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        for i, num in enumerate(nums):\n",
    "\n",
    "            if len(st) == k+1:\n",
    "                st.remove(nums[i-k-1])\n",
    "            if num in st:\n",
    "                return True\n",
    "            st.add(num)\n",
    "            # print(len(st))\n",
    "            index = bisect_left(st, num)\n",
    "            # print(st)\n",
    "            if index < len(st) - 1 and st[index + 1] - st[index] <=t: return True\n",
    "            if index >0 and st[index] - st[index-1] <=t: return True\n",
    "\n",
    "\n",
    "      \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "\n",
    "        def getIdx(u):\n",
    "            if u > 0:\n",
    "                return u // (t+1)\n",
    "            else:\n",
    "                return (u+1) // (t+1) - 1\n",
    "        \n",
    "        mp = {}\n",
    "        for i, u in enumerate(nums):\n",
    "            idx = getIdx(u)\n",
    "\n",
    "            if idx in mp:\n",
    "                return True\n",
    "            \n",
    "            l, r = idx-1, idx+1\n",
    "            if l in mp and abs(u - mp[l]) <= t:\n",
    "                return True\n",
    "            if r in mp and abs(u - mp[r]) <= t:\n",
    "                return True\n",
    "            \n",
    "            mp[idx] = u\n",
    "\n",
    "            if i >= k:\n",
    "                mp.pop(getIdx(nums[i-k]))\n",
    "        return False\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getIdx(self,num,size):\n",
    "        if num>= 0:\n",
    "            return num//size\n",
    "        else:\n",
    "            return (num+1)//size-1\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if len(nums)==0 or k==0:\n",
    "            return False\n",
    "        #print(nums)\n",
    "        bucket_map = dict()\n",
    "        idx = self.getIdx(nums[0],t+1)\n",
    "        #print(idx)\n",
    "        bucket_map[idx] = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            idx = self.getIdx(nums[i],t+1)\n",
    "            if idx in bucket_map:\n",
    "                return True\n",
    "            bucket_map[idx] = nums[i]\n",
    "\n",
    "            if idx-1 in bucket_map and bucket_map[idx-1] >= nums[i]-t:\n",
    "                return True\n",
    "            if idx+1 in bucket_map and bucket_map[idx+1] <= nums[i]+t:\n",
    "                return True\n",
    "            \n",
    "            if i>=k:\n",
    "                first_idx = self.getIdx(nums[i-k],t+1)\n",
    "                bucket_map.pop(first_idx)\n",
    "            \n",
    "            \n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        for i,num in enumerate(nums):            \n",
    "            st.add(num)\n",
    "            index=bisect_left(st,num)\n",
    "            if index<len(st)-1 and st[index+1]-st[index]<=t:return True\n",
    "            if index>0 and st[index]-st[index-1]<=t:return True\n",
    "            if len(st)>k:\n",
    "                st.remove(nums[i-k])\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        for i , num in enumerate(nums):\n",
    "            st.add(num)\n",
    "            index = bisect_left(st,num)\n",
    "            if index < len(st) - 1 and st[index+1] - st[index]<=t:\n",
    "                return True\n",
    "            if index > 0 and st[index] - st[index -1] <= t:\n",
    "                return True\n",
    "            if len(st) > k:\n",
    "                st.remove(nums[i-k])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        sort_list = SortedList([])\n",
    "        value_diff, index_diff = t, k\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            lower, upper = nums[i] - value_diff, nums[i] + value_diff\n",
    "            l = sort_list.bisect_left(lower)\n",
    "            r = sort_list.bisect_right(upper)\n",
    "            ans += r - l\n",
    "\n",
    "            # slide window\n",
    "            sort_list.add(nums[i])\n",
    "            if i-index_diff >= 0:\n",
    "                sort_list.remove(nums[i-index_diff])\n",
    "            \n",
    "        return ans >= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if not nums or k==0:\n",
    "            return False\n",
    "        array=[nums[0]]\n",
    "        left=0\n",
    "        right=1\n",
    "        array=SortedList(array)\n",
    "        while right<len(nums):\n",
    "            index=bisect_left(array,nums[right])\n",
    "            if index==0:\n",
    "                if abs(nums[right]-array[index])<=t:\n",
    "                    return True\n",
    "            elif index==len(array):\n",
    "                if abs(nums[right]-array[index-1])<=t:\n",
    "                    return True\n",
    "            else:\n",
    "                if abs(nums[right]-array[index])<=t or abs(nums[right]-array[index-1])<= t:\n",
    "                    return True\n",
    "            array.add(nums[right])\n",
    "            right+=1\n",
    "            if right-left>k:\n",
    "                array.remove(nums[left])\n",
    "                left+=1\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from bisect import bisect_left\n",
    "        from sortedcontainers import SortedList\n",
    "        INT_MIN = - 1 << 31\n",
    "        INT_MAX = -INT_MIN - 1\n",
    "        n = len(nums)\n",
    "        s = SortedList()\n",
    "        for i in range(n):\n",
    "            # 大于等于x-t的最小元素, 这里注意越界情况\n",
    "            idx = bisect_left(s, max(nums[i], INT_MIN+t)-t)\n",
    "            if idx != len(s) and s[idx] <= min(nums[i], INT_MAX-t) + t:\n",
    "                return True\n",
    "            s.add(nums[i])\n",
    "            if i >= k:\n",
    "                s.remove(nums[i-k])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if k == 0:\n",
    "            return False\n",
    "\n",
    "        sl = SortedList()\n",
    "\n",
    "        lens = len(nums)\n",
    "        l = 0\n",
    "        for r in range(lens):\n",
    "            if r - l <= k and sl:\n",
    "                rights = max(min(bisect.bisect_left(sl, nums[r]), len(sl) - 1), 0)\n",
    "                lefts = max(rights - 1, 0)\n",
    "\n",
    "                if abs(nums[r] - sl[lefts]) <= t or abs(nums[r] - sl[rights]) <= t:\n",
    "                    return True\n",
    "\n",
    "            if r - l == k:\n",
    "                sl.remove(nums[l])\n",
    "                l += 1\n",
    "\n",
    "            sl.add(nums[r])\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        s = SortedList()\n",
    "        for j, x in enumerate(nums):\n",
    "            if j > k:\n",
    "                s.discard(nums[j - k - 1])\n",
    "            s.add(x)\n",
    "            i = bisect_left(s, x)\n",
    "            if (i > 0 and s[i] - s[i - 1] <= t) or (i < len(s) - 1 and s[i + 1] - s[i] <= t):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from sortedcontainers import SortedList\n",
    "        st = SortedList()\n",
    "        for i , num in enumerate(nums):\n",
    "            st.add(num)\n",
    "            index = bisect_left(st,num)\n",
    "            if index < len(st) - 1 and st[index+1] - st[index]<=t:\n",
    "                return True\n",
    "            if index > 0 and st[index] - st[index -1] <= t:\n",
    "                return True\n",
    "            if len(st) > k:\n",
    "                st.remove(nums[i-k])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
    "        n = len(nums)\n",
    "        bucket = {}\n",
    "        b_size = t+1\n",
    "        for i in range(n):\n",
    "            if i - k -1 >= 0:\n",
    "                bucket.pop(math.floor(nums[i-k-1] / b_size))\n",
    "            b_idx = math.floor(nums[i] / b_size)\n",
    "            if b_idx in bucket:  # 相同桶里已经有元素\n",
    "                return True\n",
    "            if b_idx-1 in bucket and abs(bucket[b_idx-1]-nums[i]) <= t:\n",
    "                return True\n",
    "            if b_idx+1 in bucket and abs(bucket[b_idx+1]-nums[i]) <= t:\n",
    "                return True\n",
    "            bucket[b_idx] = nums[i]\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# nums[0] - nums[k] <= t = 10\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        sort_list = SortedList([])\n",
    "        idx_diff, value_diff = k, t\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # calculate \n",
    "            lower = nums[i] - value_diff\n",
    "            upper = nums[i] + value_diff\n",
    "            l = sort_list.bisect_left(lower)\n",
    "            r = sort_list.bisect_right(upper)\n",
    "            ans += r-l\n",
    "\n",
    "            # slide window \n",
    "            sort_list.add(nums[i])\n",
    "            if i-idx_diff >= 0:\n",
    "                sort_list.remove(nums[i-idx_diff])\n",
    "\n",
    "        return ans >= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:\n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        if indexDiff == 0:\n",
    "            return False\n",
    "        window = SortedList([nums[0]])\n",
    "        for i in range(1, len(nums)):\n",
    "            left = nums[i] - valueDiff\n",
    "            right = nums[i] + valueDiff\n",
    "            if left <= window[-1] and right >= window[0]:\n",
    "                left_pos = window.bisect_left(left)\n",
    "                right_pos = window.bisect_right(right)\n",
    "                if left_pos < right_pos:\n",
    "                    return True\n",
    "                if window[left_pos] >= left and window[left_pos] <= right:\n",
    "                    return True\n",
    "            if len(window) >= indexDiff:\n",
    "                window.remove(nums[i - indexDiff])\n",
    "            window.add(nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        sl = SortedList()\n",
    "        for r in range(n):\n",
    "            p = bisect_left(sl, nums[r])\n",
    "            if p != len(sl) and abs(sl[p] - nums[r]) <= t: return True\n",
    "            if p != 0 and abs(sl[p - 1] - nums[r]) <= t: return True\n",
    "            sl.add(nums[r])\n",
    "            if r >= k:\n",
    "                sl.remove(nums[r - k])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        sl = SortedList([-inf, inf])\n",
    "        dq = deque()\n",
    "        for x in nums:\n",
    "            dq.append(x)\n",
    "            if len(dq) > k+1: sl.remove(dq.popleft())\n",
    "            p = sl.bisect_left(x)\n",
    "            if x-sl[p-1] <= t or sl[p] - x <= t: return True\n",
    "            sl.add(x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums, k: int, t: int) -> bool:\n",
    "        if len(nums)<=1 or k==0:\n",
    "            return False\n",
    "        lis=SortedList()\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            p=lis.bisect_right(nums[i])\n",
    "            if p-1>=0:\n",
    "                if nums[i]-lis[p-1]<=t:\n",
    "                    return True\n",
    "            if p<len(lis):\n",
    "                if  lis[p]-nums[i] <= t:\n",
    "                    return True\n",
    "            lis.add(nums[i])\n",
    "            if len(lis)>k:\n",
    "                lis.discard(nums[i-k])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # 数组长度\n",
    "        n = len(nums)\n",
    "        if not n:\n",
    "            return False\n",
    "        # 定义桶字典\n",
    "        map_ = {}\n",
    "        # 桶大小\n",
    "        bottom_size = t+1\n",
    "        # 窗口大小\n",
    "        window_size = k+1\n",
    "        for i in range(n):\n",
    "            # 获取该元素的桶信息\n",
    "            buttom_id = nums[i] // bottom_size\n",
    "            # 在一个桶中\n",
    "            if buttom_id in map_ and map_[buttom_id] > i-window_size:\n",
    "                return True\n",
    "            # 左桶\n",
    "            elif buttom_id-1 in map_ and map_[buttom_id-1] > i-window_size and abs(nums[map_[buttom_id-1]]-nums[i]) <= t:\n",
    "                return True\n",
    "            # 右桶\n",
    "            elif buttom_id+1 in map_ and map_[buttom_id+1] > i-window_size and abs(nums[map_[buttom_id+1]]-nums[i]) <= t:\n",
    "                return True\n",
    "            map_[buttom_id] = i\n",
    "        print(map_)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if(k == 0 or n <= 1):\n",
    "            return False\n",
    "        nums = sorted([[num, i] for i, num in enumerate(nums)])\n",
    "        left, right = 0, 1\n",
    "        while(right < n):\n",
    "            while(left < right and nums[right][0] - nums[left][0] > t):\n",
    "                left += 1\n",
    "            if(left < right and nums[right][0] - nums[left][0] <= t):\n",
    "                for i in range(left, right):\n",
    "                    if(abs(nums[i][1] - nums[right][1]) <= k):\n",
    "                        return True\n",
    "            right += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # 数组长度\n",
    "        n = len(nums)\n",
    "        if not n:\n",
    "            return False\n",
    "        # 定义桶字典\n",
    "        map_ = {}\n",
    "        # 桶大小\n",
    "        bottom_size = t+1\n",
    "        # 窗口大小\n",
    "        window_size = k+1\n",
    "        for i in range(n):\n",
    "            # 获取该元素的桶信息\n",
    "            buttom_id = nums[i] // bottom_size\n",
    "            # 在一个桶中\n",
    "            if buttom_id in map_ and map_[buttom_id] > i-window_size:\n",
    "                return True\n",
    "            # 左桶\n",
    "            elif buttom_id-1 in map_ and map_[buttom_id-1] > i-window_size and abs(nums[map_[buttom_id-1]]-nums[i]) <= t:\n",
    "                return True\n",
    "            # 右桶\n",
    "            elif buttom_id+1 in map_ and map_[buttom_id+1] > i-window_size and abs(nums[map_[buttom_id+1]]-nums[i]) <= t:\n",
    "                return True\n",
    "            map_[buttom_id] = i\n",
    "        print(map_)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if(k == 0 or n <= 1):\n",
    "            return False\n",
    "        nums = sorted([[num, i] for i, num in enumerate(nums)])\n",
    "        left, right = 0, 1\n",
    "        while(right < n):\n",
    "            while(left < right and nums[right][0] - nums[left][0] > t):\n",
    "                left += 1\n",
    "            if(left < right and nums[right][0] - nums[left][0] <= t):\n",
    "                for i in range(left, right):\n",
    "                    if(abs(nums[i][1] - nums[right][1]) <= k):\n",
    "                        return True\n",
    "            right += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], c: int, t: int) -> bool:\n",
    "        l = SortedList()\n",
    "        i = 0\n",
    "        dic = {}\n",
    "        for j in range(0, len(nums)):\n",
    "            cur = nums[j]\n",
    "            # print(j, i, j - i)\n",
    "            while (j - i > c):\n",
    "                prev = nums[i]\n",
    "                dic[prev] -= 1\n",
    "                print(\"asd\")\n",
    "                if dic[prev] == 0:\n",
    "                    l.remove(prev)\n",
    "                i += 1\n",
    "            # print(dic)\n",
    "            if len(l) > 0:\n",
    "                a = l.bisect_left(cur)\n",
    "                b = l.bisect_right(cur)\n",
    "                options = [a, b, a + 1, a - 1, b + 1, b - 1]\n",
    "                # print(l, cur)\n",
    "                for k in range(0, len(options)):\n",
    "                    index = options[k]\n",
    "                    if index >= 0 and index < len(l) and abs(l[index] - cur) <= t:\n",
    "                        return True\n",
    "            if cur not in dic:\n",
    "                dic[cur] = 0\n",
    "            l.add(cur)\n",
    "            dic[cur] += 1 \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # #为使得下标差绝对值在k内，维护一个大小为k的滑动窗口——超时\n",
    "        # for left in range(0,len(nums)):\n",
    "        #     for j in range(left+1, left+k+1):\n",
    "        #         if j < len(nums):\n",
    "        #             if abs(nums[j]-nums[left])<=t:\n",
    "        #                 return True\n",
    "        # return False\n",
    "\n",
    "        ls = [[nums[i], i] for i in range(len(nums))]  # 记录值和其排序前的下标\n",
    "        ls.sort(key=lambda x: x[0])  # 对列表每个元素以第一个元素（值）为参考进行排序\n",
    "        for i in range(len(nums)):  # 遍历\n",
    "            for j in range(i + 1, len(nums)):  # 遍历\n",
    "                if ls[j][0] - ls[i][0] > t:  # 比较值\n",
    "                    break\n",
    "                if abs(ls[j][1] - ls[i][1]) <= k:  # 比较下标\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        # #为使得下标差绝对值在k内，维护一个大小为k的滑动窗口——超时\n",
    "        # for left in range(0,len(nums)):\n",
    "        #     for j in range(left+1, left+k+1):\n",
    "        #         if j < len(nums):\n",
    "        #             if abs(nums[j]-nums[left])<=t:\n",
    "        #                 return True\n",
    "        # return False\n",
    "        \n",
    "        # 遍历数组，记录值和其排序前的下标\n",
    "        ls = [[nums[i], i] for i in range(len(nums))]\n",
    "        ls.sort(key=lambda x: x[0])  # 对列表每个元素以第一个元素（值）为参考进行排序\n",
    "        for i in range(len(nums)):  \n",
    "            for j in range(i + 1, len(nums)): \n",
    "                if ls[j][0] - ls[i][0] > t:  # 比较值\n",
    "                    break\n",
    "                if abs(ls[j][1] - ls[i][1]) <= k:  # 比较下标\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        from sortedcontainers import SortedSet\n",
    "        if len(nums) < k + 1:\n",
    "            myset = SortedSet(nums)\n",
    "        else:\n",
    "            myset = SortedSet(nums[:k + 1])\n",
    "        if len(myset) < min(len(nums), k + 1):\n",
    "            return True\n",
    "        for i in range(len(myset) - 1):\n",
    "            if myset[i + 1] - myset[i] <= t:\n",
    "                return True\n",
    "        for i in range(k + 1, len(nums)):\n",
    "            myset.remove(nums[i - k - 1])\n",
    "            if nums[i] in myset:\n",
    "                return True\n",
    "            myset.add(nums[i])\n",
    "            tempindex = myset.index(nums[i])\n",
    "            if tempindex > 0 and nums[i] - myset[tempindex - 1] <= t:\n",
    "                return True\n",
    "            if tempindex < len(myset) - 1 and myset[tempindex + 1] - nums[i] <= t:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if not nums: return False\n",
    "        if k == 0: return False\n",
    "        n=len(nums)\n",
    "        k = min(n-1,k)\n",
    "        sst = SortedSet()\n",
    "        for i in range(k+1):\n",
    "            a = nums[i]\n",
    "            l,r = a-t,a+t\n",
    "            pl,pr=sst.bisect_left(l),sst.bisect_left(r)\n",
    "            if pl < pr: return True\n",
    "            if pr<len(sst) and sst[pr]==r: return True\n",
    "            sst.add(a)\n",
    "        for i in range(1,n-k):\n",
    "            b,a = nums[i-1],nums[i+k]\n",
    "            sst.discard(b)\n",
    "            l,r = a-t,a+t\n",
    "            pl,pr=sst.bisect_left(l),sst.bisect_left(r)\n",
    "            if pl < pr: return True\n",
    "            if pr<len(sst) and sst[pr]==r: return True\n",
    "            sst.add(a)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        if not nums: return False\n",
    "        if k == 0: return False\n",
    "        n=len(nums)\n",
    "        k = min(n-1,k)\n",
    "        sst = SortedSet()\n",
    "        for i in range(k+1):\n",
    "            a = nums[i]\n",
    "            l,r = a-t,a+t\n",
    "            pl,pr=sst.bisect_left(l),sst.bisect_left(r)\n",
    "            if pl < pr: return True\n",
    "            if pr<len(sst) and sst[pr]==r: return True\n",
    "            sst.add(a)\n",
    "        for i in range(1,n-k):\n",
    "            b,a = nums[i-1],nums[i+k]\n",
    "            sst.discard(b)\n",
    "            l,r = a-t,a+t\n",
    "            pl,pr=sst.bisect_left(l),sst.bisect_left(r)\n",
    "            if pl < pr: return True\n",
    "            if pr<len(sst) and sst[pr]==r: return True\n",
    "            sst.add(a)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
    "        s = SortedSet()\n",
    "        for i, num in enumerate(nums):\n",
    "            idx = s.bisect_left(num-t)\n",
    "            if 0<=idx <len(s) and s[idx]<=num+t:\n",
    "                return True\n",
    "            s.add(num)\n",
    "            if i>=k:\n",
    "                s.remove(nums[i-k])\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
